package Algorithm.Array;

/**
 * @Author ykeezy
 * @Date：2024/6/223:16
 * @PacakageName：
 * @ClassName：2024/6/2
 * @Description：移除元素
 * @Version 1.0
/* */

class RemoveElement {
    /*给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

        假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

        更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
        返回 k。
        原地算法的空间复杂度总是为 O(1);
        */

    /*双指针法（快慢指针法）：定义一个快指针和一个慢指针，快指针对数组进行遍历，寻找！=val的元素，
    慢指针等待快指针找到！=val类型的元素后将该元素赋值给慢指针所在元素，然后慢指针移向下一个元素。
    直到快指针完成对数组的遍历。*/
    public static int[] removeElement(int[] array, int val ){

        int fastPointer = 0;
        int slowPointer = 0;
        for (; fastPointer <= array.length - 1; fastPointer++){
            if (array[fastPointer] != val){
                array[slowPointer] = array[fastPointer];
                slowPointer++;

            }

        }

        System.out.println("k的大小为：" + slowPointer);
        return array;

    }

    //暴力解法
    public static int[] removeElementBruteForce(int[] nums, int val){

        //每移除一个元素意味着数组长度就会-1，故for循环的判断条件不能为 nums.length - 1这个常量
        int size = nums.length - 1;
        //find是向右循环的下标
        int left = 0;
        //left向右探，直至探完数组“真实有效的范围”   真实有效的范围就是保证left向右探的元素都是没有被探过的元素的范围。
        for (; left <= size;){
            //若nums[left] == val，则将整个数组向前移一位
            if (nums[left] == val){
                for (int removePlace = left; removePlace < nums.length-1 ; removePlace++) {
                    nums[removePlace] = nums[removePlace+1];
                }
                //由于整个数组向左移了一位，故数组的”真实有效的范围“就少了一位，故有size--
                size --;
            }else {
                //若 != val，则将left+1继续向右探
                left++;

            }

        }
        System.out.println("k的大小为:" + (size + 1));
        return nums;

    }

    public static void main(String[] args) {

        for (int i:removeElement(new int[]{3,2,2,3}, 3)
        ) {
            System.out.println(i);

        }

        for (int i:removeElementBruteForce(new int[]{3,2,2,3}, 3)
             ) {
            System.out.println(i);

        }

    }

}

/*    给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

        考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

        更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
        返回 k 。*/
class RemoveDuplicates{

    /*依然采用快慢指针法进行解题，快指针先行向数组右侧探索，直到找到一个值与慢指针不同的值，然后停下来用该值覆盖慢指针后面的一个元素，如此往复
    直到数组被完全遍历。*/
    public static int[] removeDuplicates (int[] nums){
        int fastPointer = 0;
        int slowPointer = 0;
        int k = 1;
        for (; fastPointer <= nums.length - 1; fastPointer++){
            if (nums[fastPointer] != nums[slowPointer]){
                nums[++slowPointer] = nums[fastPointer];
                k++;
            }

        }
        System.out.println("新数组长度：" + k);

        return nums;

    }

    public static void main(String[] args) {
        for (int i:removeDuplicates(new int[]{1,1,2})
             ) {
            System.out.println(i);
        }

    }

}

/*
    给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

        注意：如果对空文本输入退格字符，文本继续为空。

        示例 1：
        输入：s = "ab#c", t = "ad#c"
        输出：true
        解释：s 和 t 都会变成 "ac"。*/
class BackspaceCompare{

    //双指针法
    //一个指针瞄准串s，另一个指针瞄准串t，两个指针同时从右向左移
    public static boolean doublePointerBackspaceCompare(String s, String t){
        //SkipCount是用来存储'#'数量的变量
        int sSkipCount = 0;
        int tSkipCount = 0;
        //Length是串s与串t的初始长度
        int sLength = s.length() - 1;
        int tLength = t.length() - 1;
        while (true){
            //sLength < 0则串s已遍历完毕
            while (sLength >= 0){
                //从后往前遍历，若遍历到的char =! '#'，判断SkipCount是否>0，若是则SkipCount--，若不是则跳出循环。
                //若char == '#',则将SkipCount++
                if (s.charAt(sLength) != '#'){
                    if (sSkipCount > 0){
                        sSkipCount --;
                    }else break;
                }else {
                    sSkipCount ++;
                }
                //执行到这一步说明SkipCount >0，需要将sLength向左移继续检查左边还有没有'#'，故需要sLength--；
                sLength--;

            }
            //串t的代码与串s同理，不过多赘述
            while (tLength >= 0){
                if (t.charAt(tLength) != '#'){
                    if (tSkipCount > 0){
                        tSkipCount --;
                    }else break;
                }else {
                    tSkipCount ++;
                }

                tLength --;

            }
            //若Slength 或 Tlength有一个<0，则说明至少一个串已经遍历完成
            if (sLength < 0 || tLength <0){
                //若满足sLength == -1 && tLength == -1，则说明两个串同时结束遍历，意味着两个串从头到位的字符都是匹配的，故return true
                if (sLength == -1 && tLength == -1){
                    return true;
                    //若不满足sLength == -1 && tLength == -1，则说明一个串的真实长度 < 另一个串的真实长度，故return false
                }else return false;
            }

            //若索引位置的字符相同，则两个串的索引集体向左移，准备下一个字符的比对
            if (s.charAt(sLength) == t.charAt(tLength)){
                sLength --;
                tLength --;
            }else {
                //若不同，说明串不同，return false
                return false;
            }

        }

    }

    //栈写法
    public static boolean backspaceCompare(String s,String t){
        if (getRealString(s).equals(getRealString(t))){
            return true;
        }else return false;

    }
    public static String getRealString(String str){

        //声明一个StringBuffer
        StringBuffer stringBuffer = new StringBuffer();
        //定义StringBuffer的下标
        int newStrIndex = 0;
        for (int left = 0; left <= str.length() - 1; left++) {
            //若原串下标位置 != '#'，则存入stringBuffer
            if (str.charAt(left) != '#'){
                stringBuffer.append(str.charAt(left));
                newStrIndex++;
            }else{
                //若原串下标位置 == '#'，则将stringBuffer下标向左移然后删除该元素。
                if (newStrIndex > 0){
                    stringBuffer.deleteCharAt(--newStrIndex);
                }

            }

        }

        return stringBuffer.toString();

    }

    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab#c","ad#c"));

    }


}
